//============================================================================
// Name        : problem101.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

vector <long int> getSequence(int length) {
	vector <long int> seq;
	for (int i = 1; i <= length; i++) {
		seq.push_back((1 + pow(i, 11.0))/(1+i));
	}
	/*for (int i = 1; i <= length; i++) {
		seq.push_back(pow(i, 3.0));
	}*/
	return seq;
}

long lagrange(vector<long int> points, int term) {
	long int result = 0;
	for(int i = 1; i < term; i++) {
		long int den = 1, num = 1;
		for(int j = 1; j < term; j++) {
			if (j == i) continue;
			num *= (term - j);
			den *= (i -j);

		}
		//cout<<num<<" "<<den<<" "<<num/den<<" "<<i<<endl;
		result += (num/den)*points.at(i - 1);
	}
	return result;
}

int main() {
	vector<long int> seq = getSequence(111);
	long int sum = 1, next = 0;
	for(int i = 3; ; i++) {
		next = lagrange(seq, i);
		cout<<next<<" ";
		if (next == seq.at(i-1)) {
			cout<<endl<<next<<" Found"<<endl;
			break;
		}
		sum += next;
	}
	cout<<endl;
	cout<<sum<<endl;

	return 0;
}
